/*
给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

例如：
给定二叉树 [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
返回其自底向上的层次遍历为：

[
  [15,7],
  [9,20],
  [3]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> res;
        if(root==NULL){
            return res;
        }
        queue<TreeNode*> myqueue;
        myqueue.push(root);
        stack<vector<int>> mystack;
        int que_len=0;
        TreeNode* cur=NULL;
        vector<int> layer;
        while(!myqueue.empty()){
            que_len=myqueue.size();
            layer.clear();
            while((que_len--)>0){
                cur=myqueue.front();
                layer.push_back(cur->val);
                myqueue.pop();
                if(cur->left!=NULL){
                    myqueue.push(cur->left);
                }
                if(cur->right!=NULL){
                    myqueue.push(cur->right);
                }
            }
            mystack.push(layer);
        }
        
        while(!mystack.empty()){
            res.push_back(mystack.top());
            mystack.pop();
        }
        return res;
    }
};